package B刷题.二叉树;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * @author wei.zhao
 * @description: 102.二叉树的层序遍历
 * @date 2022年11月09日 17:27
 */
public class Code04_LevelOrder {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        LinkedList<TreeNode> list = new LinkedList<>();
        HashMap<TreeNode, Integer> levelMap = new HashMap<>();
        list.add(root);
        levelMap.put(root, 0);
        while (!list.isEmpty()) {
            TreeNode pop = list.pop();
            Integer level = levelMap.get(pop);
            if (level == result.size()) {
                result.add(new ArrayList<>());
            }
            List<Integer> levelList = result.get(level);
            levelList.add(pop.val);
            if (null != pop.left) {
                list.add(pop.left);
                levelMap.put(pop.left, level + 1);
            }
            if (null != pop.right) {
                list.add(pop.right);
                levelMap.put(pop.right, level + 1);
            }
        }
        return result;
    }

}
